package test;

public class FindTargetSumWays {
	public int findTargetSumWays(int[] nums, int target) {
		
        int sum=0,n=nums.length;
        for(int x:nums) sum+=x;
        int aim=(sum+target)/2;
        
        if((sum+target)%2!=0||aim<0) return 0;
        
        int[][] dp=new int[n+1][aim+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=aim;j++){   //背包问题j可以从0开始
                dp[i][j]=dp[i-1][j];
                if(j-nums[i-1]>=0)
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][aim];
    }
}
